package org.getOffer;

/**
 * @Author yu
 * @Date 2021/7/6
 */
public class Practice12 {

    public static void main(String[] args) {

        Practice12 practice12 = new Practice12();

        //char[][] chars = {{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
        char[][] chars = {{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
        //char[][] chars = {{'A','B'},{'C','D'}};
        //char[][] chars = {{'A'}};
        //char[][] chars = {{'A','A'}};
        //char[][] chars = {{'A','B'},{'C','D'}};
        String str = "SEE";

        System.out.println(practice12.exist(chars, str));

    }

    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length; j++) {
                if(dfs(board, words, i, j, 0)) return true;
            }
        }
        return false;
    }
    boolean dfs(char[][] board, char[] word, int i, int j, int k) {
        if(i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k]) return false;
        if(k == word.length - 1) return true;
        board[i][j] = '\0';
        boolean res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) ||
                dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i , j - 1, k + 1);
        board[i][j] = word[k];
        return res;
    }

//    char[] chars;
//    StringBuilder stringBuilder;
//    int[][] temp;

//    public boolean exist(char[][] board, String word) {
//
//        chars = word.toCharArray();
//
//        stringBuilder = new StringBuilder();
//
//        temp = new int[board.length][board[0].length];
//
//        for (int i=0;i<board.length;i++){
//
//            for (int j=0;j<board[0].length;j++){
//
////                if (board[i][j]==chars[0]){
////
////                    stringBuilder.append(chars[0]);
////
////                    temp[i][j] = 1;
////
////                    dfs(i+1,j,board,1);
////
////                    dfs(i,j+1,board,1);
////
////                    dfs(i-1,j,board,1);
////
////                    dfs(i,j-1,board,1);
////
////                    break LOOK;
////
////                }
//
//                if (dfs(i,j,board,0)) {
//                    return true;
//                }
//
//            }
//
//        }
//
//        return false;
//        //return stringBuilder.length()==word.length();
//
//    }
//
//    public boolean dfs(int line,int row,char[][] board,int index){
//
//        if (line==board.length||row==board[0].length||line<0||row<0||board[line][row]==0||index==chars.length||temp[line][row]==1){
//            return false;
//        }
//
//        if (board[line][row]!=chars[index]){
//            return false;
////            stringBuilder.append(chars[index]);
////
////            temp[line][row] = 1;
////
////            System.out.println(index);
//
//        } else {
//            return true;
//        }
//        return dfs(line+1,row,board,index+1)||dfs(line,row+1,board,index+1)||dfs(line,row-1,board,index+1)||dfs(line-1,row,board,index+1);
//
//
//    }

}
